The present invention relates to machine learning and more specifically to training a machine to classify images according to whether or not they correspond to an object of interest. A good example of an object of interest is a person's face. The images can be entire images or sub-regions of larger images.
One training technique involves obtaining a set of positive images that correspond to the object of interest and a set of negative images that do not correspond to the object of interest, and training the machine to distinguish between the two sets of images. This training technique is referred to as “supervised learning”.
One approach to performing supervised learning is known as “boosting.” Boosting is based on the principle of the committee machine. That principle states that the results of multiple, independently trained classifiers can be combined to obtain an aggregate classifier with an overall error rate that is lower than that of any of the individual classifiers.
Boosting is an iterative training process. During each iteration, an individual classifier is trained and the trained classifier is added to the aggregate classifier. The training process ends when a pre-defined stopping condition is reached. For example, the stopping condition can be a target accuracy level for the aggregate classifier or a maximum time interval for the training process.
Boosting is a well-known technique. The boosting technique was presented at the Mathematical Sciences Research Institute Workshop on Nonlinear Estimation and Classification in 2002 and is also described in the paper, “The boosting approach to machine learning: an overview”, by Robert Shapire and published at: http://www.cs.princeton.edu/˜schapire/publist.html. The contents of this paper are incorporated herein by reference.
A common form of boosting is known as Adaboost. The Adaboost technique was developed by Yoav Freund and Robert Shapire and is described in the paper, “A decision-theoretic generalization of on-line learning and an application to boosting”, Journal of Computer and System Sciences, Volume 55(1), pages 119-139, August 1997. The contents of this paper are incorporated herein by reference.
The Adaboost algorithm has been applied successfully to a number of machine learning problems. In particular, it has been applied to image classification, as described in the paper, “Robust Real-Time Object Detection”, by Paul Viola and Michael J. Jones International Conference on Computer Vision, presented at IEEE Computer Society's 2001 International Conference on Computer Vision, and also published at: http://www.hpl.hp.com/techreports/Compaq-DEC/CRL-2001-1.html. The application of Adaboost to image classification is also described in the paper, “Rapid Object Detection using a Boosted Cascade of Simple Features”, presented at IEEE Computer Society's 2001 Computer Vision and Pattern Recognition Conference. The contents of both of these papers are incorporated herein by reference.
Other forms of boosting exist, for example, bagging, arcing and leveraging. These techniques are described further in the paper “An Introduction to Boosting and Leveraging”, by Ron Meir and Gunnar Raetsch and published at: http://www.boosting.org/papers/MeiRae03.pdf, and also published in Lecture Notes In Artificial Intelligence, Advanced Lectures On Machine Learning Archive, pages 118-183, 2003. The contents of this paper are incorporated herein by reference.
A classifier that is trained using boosting is typically very fast at classifying images. However, the training process is extremely slow, thereby limiting the applicability of boosting as a technique for training classifiers.